• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    用於處理器之複數個指令排程方法，該排程方法之步驟包含建立一包含複數行之功能單元資源表，每一行係相對應於該處理器之複數個操作循環之一及包含複數個欄位，每一欄位係相對應於該處理器之一功能單元；建立一乒乓資源表，其包含複數個行，每一行係相對應於該處理器之複數個操作循環之一及包含複數個欄位，每一欄位係相對應於該處理器之一暫存器庫之一讀取端口或一寫入端口以及分配複數個指令至該處理器之該複數個操作循環及註冊相對應於該些已分配指令之該些功能單元及該些暫存器庫之該些端口於該功能單元資源表及該乒乓資源表。
    公开号:TW201305913A
    申请号:TW101122344
    申请日:2012-06-22
    公开日:2013-02-01
    发明作者:Jenq-Kuen Lee；Yu-Te Lin；Chung-Ju Wu
    申请人:Nat Univ Tsing Hua；
    IPC主号:G06F9-00
    专利说明:
    用於處理器之複數個指令排程方法
    本發明係關於一處理器之一種複數個指令之排程方法，特別是一具有分散式暫存器檔案之處理器之一種複數個指令排程方法。
    高性能數位訊號處理器(DSPs)逐漸增加運用具有超長指令集(VLIW)資料路徑結構之指令層式的平行(Instruction-level parallelism,ILP)，上述之數位訊號處理器通常具有複數個功能單元。另，連接暫存器的讀取端口及寫入端口的數量會隨著功能單元的數量增加而增加。
    為了減少暫存器之讀取端口及寫入端口的數量，因此採用分散式暫存器檔案的設計。分散式暫存器檔案的設計具有一些特點，例如：複數個叢集暫存器檔案、複數個暫存器庫及有限制的暫時性相連，例如：乒乓結構。當為於超長指令集結構維持高指令層式的平行，上述之特點能夠減少暫存器之讀取端口/寫入端口的數量及減少功率消耗。
    圖1係為使用分散式暫存器檔案及一乒乓結構之一平行架構核心處理器之結構示意圖。該平行架構核心處理器10包含一第一叢集12A及一第二叢集12B。其中該第一叢集12A及該第二叢集12B各包含一第一功能單元20、一第二功能單元30、一第一局部暫存器檔案14、一第二局部暫存器檔案16及一總體暫存器檔案(global register file)22。
    其中該第一局部暫存器檔案14係連接至該第一功能單元20，該第二局部暫存器檔案16係連接至該第二功能單元30。另，該總體暫存器檔案22具有一乒乓結構，其中該乒乓結構係由一第一暫存器庫B1及一第二暫存器庫B2所形成。每一暫存器檔案包含複數個暫存器。
    該平行架構核心處理器10包含一第三功能單元40，其中該第三功能單元40係獨立於該第一叢集12A及該第二叢集12B之外。一第三局部暫存器檔案18係連接於該第三功能單元40。該第一功能單元20係為一載入/儲存單元(M單元)，該第二功能單元30係為一算數單元(I單元)及該第三功能單元40係為一純量單元(B單元)。
    該第三功能單元40控制分支操作及能夠執行簡單的載入/儲存及位址運算。另，該第一局部暫存器檔案14、該第二局部暫存器檔案16及該第三局部暫存器檔案18僅可被M單元20、I單元30及B單元40分別存取。該總體暫存器檔案22之每一暫存器庫僅具有一單一存取端口組，其經配置以被該M單元20及I單元30所共用。
    該總體暫存器檔案22之該些暫存器庫B1及B2之每一存取端口於一操作循環時，僅可被該第一功能單元20或該第二功能單元30之一所存取。因此，該兩工能單元20及30於每一操作循環時，僅可存取該暫存器資料庫B1或該暫存器資料庫B2之不同存取端口。上述係為該乒乓結構之存取限制條件。
    當編譯器欲產生多媒體應用程式之有效程式碼，現存之分散式暫存器檔案結構的多個特色對於編譯器(Compiler)而言係為需克服之多重挑戰。現存之分散式暫存器檔案結構的多個特色係為具有複數個叢集、複數個暫存器庫檔案及具有內嵌式超長指令集之數位訊號處理器。
    因此，針對具有叢集之結構的編譯器最佳化之研究，其係解決如何分配複數個暫存器檔案以使該些暫存器檔案能夠與指令排程運作及如何分配複數個叢集暫存器檔案之迴圈。然而，如該乒乓結構未被使用於一習知的指令排程方法，則較難達成程式設計者期望之指令排程結果。
    鑑於上述問題，本發明提供一種複數個指令之排程方法，藉以解決先前技術所存在的問題。
    本發明之一實施例係為一種複數個指令之排程方法，其應用於一處理器，該處理器包含一第一叢集及一第二叢集，每一叢集包含一第一功能單元、一第二功能單元、一連接至該第一功能單元之第一局部暫存器檔案、一連接至該第二功能單元之第二局部暫存器檔案及一總體暫存器檔案，該總體暫存器檔案具有一乒乓結構，其係由一第一暫存器庫及一第二暫存器庫所形成，該總體暫存器檔案連接至該第一功能單元及該第二功能單元，該排程方法之步驟包含建立一包含複數行之功能單元資源表，每一行係相對應於該處理器之複數個操作循環之一及包含複數個欄位，每一欄位係相對應於該處理器之一功能單元；建立一乒乓資源表，其包含複數個行，每一行係相對應於該處理器之複數個操作循環之一及包含複數個欄位，每一欄位係代表該處理器之一暫存器庫之一讀取端口或一寫入端口以及分配該複數個指令至該處理器之該複數個操作循環及註冊相對應於該些已分配指令之該些功能單元及該些暫存器庫之該些端口於該功能單元資源表及該乒乓資源表。
    上文已經概略地敍述本揭露之技術特徵，俾使下文之本揭露詳細描述得以獲得較佳瞭解。構成本揭露之申請專利範圍標的之其它技術特徵將描述於下文。本揭露所屬技術領域中具有通常知識者應可瞭解，下文揭示之概念與特定實施例可作為基礎而相當輕易地予以修改或設計其它結構或製程而實現與本揭露相同之目的。本揭露所屬技術領域中具有通常知識者亦應可瞭解，這類等效的建構並無法脫離後附之申請專利範圍所提出之本揭露的精神和範圍。
    圖2係為本發明一實施例之一平行架構核心處理器之排程方法流程示意圖。圖2所示之排程方法可用於圖1所示之該平行架構核心處理器10，於此一實施例中，該第一暫存器庫B1包含暫存器d0~d7，該第二暫存器庫B2包含暫存器d8~d15。在步驟201中，利用一虛假排程演算法(pseudo scheduler)產生該平行架構核心處理器10之複數個指令之循環資訊(cycle information)。在步驟202中，提供一具有時序圖(With Timing Graph，WTG)之創新乒乓察覺局部有利(ping-pong-aware local-favorable，PALF)之計畫(scheme)。於步驟203中，根據該循環資訊對該平行架構核心處理器10進行暫存器分配。於步驟204中，執行一乒乓察覺(ping pong aware)實體指令排程。
    因此，經由圖2之步驟201至步驟203可以達成該平行架構核心處理器10之暫存器的分配。另，剩餘之步驟204係提供該平行架構核心處理器10之一排程演算法，該步驟執行該平行架構核心處理器10之一實體指令排程。
    圖3係為對處理器進行複數個指令排程之傳統方法之流程示意圖。如圖3所示，該傳統排程方法使用一種普通的排程演算法，該普通的排程演算法包含一功能單元資源表。該功能單元資源表包含相對應於該平行架構核心處理器10之該些操作循環之複數個行(column)。每一行包含複數個欄位(field)，每一欄位係代表該平行架構核心處理器10之一功能單元(functional unit)，例如：M1代表該叢集12A之該M單元20，I1代表該叢集12A之該I單元30，M2代表該叢集12B之該M單元20，I2代表該叢集12B之該I單元30及B1代表該B單元40。
    圖3亦顯示該平行架構核心處理器10之三種指令。由於該平行架構核心處理器10使用超長指令集架構(very long instruction word，VLIW)，因此可於一操作循環內執行一或多個指令。於此一實施例中，於一操作循環內執行之該些指令可被包裹成一指令組合包(bundle)，其中如圖3所示，至多五個指令(對應於該平行架構核心處理器10之該些功能單元之數量)能於一操作循環內執行。
    該第一指令[C1m：1w d1,sp,0]使用該叢集12A之該M單元20，因此該功能單元資源表之該目前操作循環之該欄位M1被檢查。該第二指令[C1i：addi d2,d3,0]係使用該叢集12A之該I單元30，因此該功能單元資源表之該目前操作循環之該欄位I1被檢查。該第三指令[C1m：movi d8,1]係使用該叢集12A之該I單元30。
    另，由於該功能單元資源表之該目前操作循環之該欄位I1已被檢查，該第三指令[C1m：movi d8,1]被排程至下一操作循環。如圖3所示，該第一指令[C1m：1w d1,sp,0]及該第二指令[C1i：addi d2,d3,0]被排程於指令組合包1，第三指令[C1m：movi d8,1]被排程於指令組合包2。
    由於該平行架構核心處理器10使用具有一乒乓結構之一總體暫存器檔案，該些指令之排程需符合該乒乓結構的存取限制。另，該乒乓結構係由該第一暫存器庫B1及該第二暫存器庫B2所形成。意即，於一單一操作循環之時間內，一或多個功能單元無法存取一暫存器庫之一讀取及輸入端口。換句話說，如於一操作循環之時間內，一功能單元存取一暫存器庫之該讀取端口時，另一功能單元則無法存取該讀取端口。因此，當該些暫存器d1及d2皆屬於該第一暫存器庫B1時，如該第一指令[C1m：1w d1,sp,0]及該第二指令[C1i：addi d2,d3,0]於該同一操作循環之時間內，皆被排程以存取該第一暫存器庫，則會違反該乒乓結構限制。因此，需要另一操作循環以執行在組合包1中所排定的該些指令。
    其結果是，如圖3所示，於進一步排程之後，該第一指令[C1m：1w d1,sp,0]係被排程於組合包1，該第二指令[C1i：addi d2,d3,0]係被排程於組合包2，該第三指令[C1m：movi d8,1]係被排程於組合包3。但，由於該排程方法並未事先考慮該平行架構核心處理器10之該乒乓結構，因此該排程結果不是一最佳結果。
    圖4係為本發明一實施例之一處理器之複數個指令之排程方法流程示意圖。圖4所示之排程方法可被應用於圖1之該平行架構核心處理器10。於步驟401中，建立一功能單元資源表並執行步驟402，其中該功能單元資源表包含複數個行，每一行係相對應於該處理器之複數個操作循環中之一操作循環。另，每一行係包含複數個欄位，其中每一欄位係相對應於該處理器之一功能單元。
    於步驟402中，建立一乒乓資源表並執行步驟403，其中該乒乓資源表包含複數個行，每一行係相對應於該處理器之複數個操作循環中之一操作循環。另，每一行係包含複數個欄位，其中每一欄位係相對應於該處理器之一暫存器庫之一讀取端口或一寫入端口。於步驟403中，分配複數個指令至該處理器之複數個操作循環，以及註冊相對應於該已分配指令之該些功能單元於該功能單元資源表及註冊相對應於該已分配指令之該些暫存器庫之該些端口於該乒乓資源表。
    圖5係為本發明一實施例之一處理器之複數個指令之排程過程示意圖。圖5所示之排程過程係相似圖3所示之排程過程，其亦具有三個指令需被排程。然而，相異於圖3所示之該排程過程，除了該功能單元資源表之外，亦建立一乒乓資源表。該乒乓資源表之一行之每一欄位係係代表該平行架構核心處理器10之一暫存器庫之一讀取端口或一寫入端口。
    即，每一行係包含八個欄位，分別為R1、R2、R3、R4、W1、W2、W3及W4。
    R1係相對應於該叢集12A之該第一暫存器庫B1之該讀取端口，R2係對應於該叢集12A之該第二暫存器庫B2之該讀取端口，R3係相對應於該叢集12B之該第一暫存器庫B2之該讀取端口，R4係相對應於該叢集12B之該第二暫存器庫B2之該讀取端口，W1係相對應於該叢集12A之該第一暫存器庫B1之該寫入端口，W2係相對應於該叢集12A之該第二暫存器庫B2之該寫入端口，W3係相對應於該叢集12B之該第一暫存器庫B1之該寫入端口及W4係相對應於該叢集12B之該第二暫存器庫B2之該寫入端口。
    於此一實施例中，步驟403係以逐週期(cycle by cycle)的方式而執行。意即，該些被排程於現行該操作循環(present operation cycle)之指令會於該下一操作循環的排程之前被配發(allotted)。因此，於該下一操作循環之該排程之前，所有已被排程之該些指令需被檢查以判斷該些指令是否已排程於該目前操作循環。回到圖5，該第一指令[C1m：1w d1,sp,0]使用該叢集12A之該M單元20及存取該叢集12A之該第一暫存器庫B1之該讀取端口。因此該第一指令[C1m：1w d1,sp,0]係被分配至組合包1及該功能單元資源表之該目前操作循環之該欄位M1及該乒乓資源表之該目前操作循環之該欄位W1皆被註冊。該第二指令[C1i：addi d2,d3,0]使用該叢集12A之該I單元30及存取該叢集12A之該第一暫存器庫B1之該寫入端口。
    由於該乒乓資源表之該目前操作循環之該欄位W1已被註冊，則該第二指令[C1i：addi d2,d3,0]將被忽略直到下一操作循環出現。該第三指令[C1m：movi d8,1]使用該叢集12A之I單元30及該叢集12A之第二暫存器庫B2之該寫入端口。因此，該第三指令[C1m：movi d8,1]係被分配至組合1及該功能單元資源表之該目前操作循環之該欄位I1及該乒乓資源表之該目前操作循環之該欄位W2皆被註冊。於下一操作循環時，該第二指令[C1i：addi d2,d3,0]係被分配至組合包2。
    比較圖5所示之排程結果及圖3所示之排程結果，圖4所示之排程方法之排程結果相較於習知之排程方法之排程結果，圖4所示之排程方法使用較少的操作循環。因此，本發明所提供之一處理器之複數個指令之排程方法係使用一功能單元資源表及一乒乓資源表。另，該乒乓結構之存取限制條件係被該排程方法所採用。
    本揭露之技術內容及技術特點已揭示如上，然而熟悉本項技術之人士仍可能基於本揭露之教示及揭示而作種種不背離本揭露精神之替換及修飾。因此，本揭露之保護範圍應不限於實施例所揭示者，而應包括各種不背離本揭露之替換及修飾，並為以下之申請專利範圍所涵蓋。
    10‧‧‧平行架構核心處理器
    12A‧‧‧第一叢集
    12B‧‧‧第二叢集
    14‧‧‧第一局部暫存器檔案
    16‧‧‧第二局部暫存器檔案
    18‧‧‧第三局部暫存器檔案
    20‧‧‧M單元
    22‧‧‧總體暫存器檔案
    30‧‧‧I單元
    40‧‧‧B單元
    201~204‧‧‧步驟
    401~403‧‧‧步驟
    圖1係為使用分散式暫存器檔案及一乒乓結構之一平行架構核心處理器之結構示意圖；圖2係為本發明一實施例之一平行架構核心處理器之排程方法流程示意圖；圖3係為一處理器之複數個指令的習知排程方法之過程示意圖；圖4係為本發明一實施例之一處理器之複數個指令之排程方法流程示意圖；及圖5係為本發明一實施例之一處理器之複數個指令之排程過程示意圖。
    201~204‧‧‧步驟
    权利要求:
    Claims (8)
    [1] 一種用於處理器之複數個指令排程方法，該處理器包含一第一叢集及一第二叢集，每一叢集包含一第一功能單元、一第二功能單元、一連接至該第一功能單元之第一局部暫存器檔案、一連接至該第二功能單元之第二局部暫存器檔案及一總體暫存器檔案，該總體暫存器檔案具有一乒乓結構，該乒乓結構係由一第一暫存器庫及一第二暫存器庫所形成，該總體暫存器檔案總體暫存器檔案連接至該第一功能單元及該第二功能單元，該排程方法包含以下步驟：建立一包含複數行之功能單元資源表，每一行係相對應於該處理器之複數個操作循環之一及包含複數個欄位，每一欄位係代表該處理器之一功能單元；建立一包含複數行之乒乓資源表，每一行係相對應於該處理器之複數個操作循環之一及包含複數個欄位，每一欄位係代表該處理器之一暫存器庫之一讀取端口或一寫入端口；以及分配複數個指令至該處理器之該複數個操作循環及註冊相對應於該些已分配指令之該些功能單元及該些暫存器庫之該些端口於該功能單元資源表及該乒乓資源表。
    [2] 如請求項第1項所述之排程方法，其中分配複數個指令至該處理器之該複數個操作循環及註冊相對應於該些已分配指令之該些功能單元及該些暫存器庫之該些端口於該功能單元資源表及該乒乓資源表之步驟更包含以下次步驟：如相對應於該目前操作循環之該行之該已分配指令之該功能單元資源表之代表該些功能單元之該欄位及該乒乓資源表之該些暫存器庫之該些端口之該欄位皆未註冊時，分配一或多個複數個指令至一目前操作循環；註冊相對應於該已分配指令之該些功能單元於該功能單元資源表及該些暫存器庫之該些端口於該乒乓資源表；以及設定一下一操作循環為該目前操作循環及重複次步驟如相對應於該目前操作循環之該行之該已分配指令之該功能單元資源表之相對應於該些功能單元之該欄位及該乒乓資源表之該些暫存器庫之該些端口之該欄位皆未註冊時，分配一或多個複數個指令至一目前操作循環及次步驟註冊相對應於該已分配指令之該些功能單元於該功能單元資源表及該些暫存器庫之該些端口於該乒乓資源表。
    [3] 如請求項第1項所述之排程方法，其中該步驟分配該複數個指令至該處理器之該複數個操作循環及註冊相對應於該些已分配指令之該些功能單元及該些暫存器庫之該些端口於該功能單元資源表及該乒乓資源表更包含以下次步驟：檢視該些指令之一；如相對應於該目前操作循環之該行之該已檢視指令之該功能單元資源表之相對應於該些功能單元之該欄位及該乒乓資源表之該些暫存器庫之該些端口之該欄位皆未註冊時，分配該已檢視指令至一目前操作循環；如相對應於該目前操作循環之該行之該已檢視指令之該功能單元資源表之相對應於該些功能單元之該欄位之一及該乒乓資源表之該些暫存器庫之該些端口之該欄位之一未註冊時，忽略該已檢視指令；註冊相對應於該已分配指令之該些功能單元及該些暫存器庫之該些端口於該功能單元資源表及該乒乓資源表；以及重複檢視該些指令之一之步驟直到檢視完所有指令及設定一下一操作循環為該目前操作循環。
    [4] 如請求項第1項所述之排程方法，其中該第一暫存器庫具有八個暫存器。
    [5] 如請求項第1項所述之排程方法，其中該第二暫存器庫具有八個暫存器。
    [6] 如請求項第1項所述之排程方法，其中該第一功能單元係為一載入/儲存單元。
    [7] 如請求項第1項所述之排程方法，其中該第二功能單元係為一算數單元。
    [8] 如請求項第1項所述之排程方法，其中該處理器更包含一第三功能單元及一第三局部暫存器檔案，其中，該第三功能單元經配置以連接於該第一叢集及該第二叢集之間，該第三局部暫存器檔案經配置以連接該第三功能單元。
    类似技术:
    公开号 | 公开日 | 专利标题
    US9672035B2|2017-06-06|Data processing apparatus and method for performing vector processing
    Liu et al.2010|A PRET architecture supporting concurrent programs with composable timing properties
    JP2018501564A|2018-01-18|プロセッサ・コアのための実行ユニット回路、プロセッサ・コア、およびプロセッサ・コア内のプログラム命令を実行する方法
    KR101966712B1|2019-04-09|분할가능한 엔진에 의해 인스턴스화된 가상 코어를 이용한 코드 블록의 실행을 지원하는 메모리 프래그먼트
    US20170235578A1|2017-08-17|Method and Apparatus for Scheduling of Instructions in a Multi-Strand Out-Of-Order Processor
    KR20140027299A|2014-03-06|이종 코어의 자동 부하 균형
    Sadrosadati et al.2018|LTRF: Enabling high-capacity register files for GPUs via hardware/software cooperative register prefetching
    US7315935B1|2008-01-01|Apparatus and method for port arbitration in a register file on the basis of functional unit issue slots
    TWI444888B|2014-07-11|基於週期資訊之處理器的暫存器配置方法
    JP2006523883A|2006-10-19|Ｉｌｐ及びｔｌｐを利用する再構成可能なプロセッサアレイ
    US20110119468A1|2011-05-19|Mechanism of supporting sub-communicator collectives with o| counters as opposed to one counter for each sub-communicator
    Yazdanpanah et al.2013|Analysis of the task superscalar architecture hardware design
    Wang et al.2016|Performance-centric register file design for GPUs using racetrack memory
    US8490071B2|2013-07-16|Shared prefetching to reduce execution skew in multi-threaded systems
    TWI464682B|2014-12-11|用於處理器之複數個指令排程方法
    Singh2021|Communication Coroutines For Parallel Program Using DW26010 Many Core Processor
    TWI396132B|2013-05-11|非規則性暫存器集之指令管線化方法
    Jatala et al.2016|Improving gpu performance through resource sharing
    KR20150101870A|2015-09-04|메모리의 뱅크 충돌을 방지하기 위한 방법 및 장치
    Chen et al.2016|Data‐aware task scheduling on heterogeneous hybrid memory multiprocessor systems
    Jing et al.2016|Bank stealing for a compact and efficient register file architecture in GPGPU
    KR20150051083A|2015-05-11|재구성 가능 프로세서, 재구성 가능 프로세서의 구성 메모리의 사용을 최적화하는 방법 및 장치
    Goel et al.2014|Shared-port register file architecture for low-energy VLIW processors
    Belviranli et al.2014|A paradigm shift in GP-GPU computing: task based execution of applications with dynamic data dependencies
    TW201543357A|2015-11-16|基於同時多執行緒（ｓｍｔ）的中央處理單元以及用於檢測指令的資料相關性的裝置
    同族专利:
    公开号 | 公开日
    US20130024666A1|2013-01-24|
    TWI464682B|2014-12-11|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US6629312B1|1999-08-20|2003-09-30|Hewlett-Packard Development Company, L.P.|Programmatic synthesis of a machine description for retargeting a compiler|
    US6523173B1|2000-01-11|2003-02-18|International Business Machines Corporation|Method and apparatus for allocating registers during code compilation using different spill strategies to evaluate spill cost|
    US7086045B2|2001-10-19|2006-08-01|Sun Microsystems, Inc.|Heuristic to improve register allocation using pass degree|
    US7069548B2|2002-06-28|2006-06-27|Intel Corporation|Inter-procedure global register allocation method|
    JP3896087B2|2003-01-28|2007-03-22|松下電器産業株式会社|コンパイラ装置およびコンパイル方法|
    TWI307478B|2005-10-26|2009-03-11|Nat Univ Tsing Hua|Method for scheduling instructions for clustered digital signal processors and method for allocating registers using the same|
    US20070239970A1|2006-04-06|2007-10-11|I-Tao Liao|Apparatus For Cooperative Sharing Of Operand Access Port Of A Banked Register File|
    US7650598B2|2006-08-09|2010-01-19|National Tsing Hua University|Method for allocating registers for a processor|
    TWI396132B|2008-08-06|2013-05-11|Nat Univ Tsing Hua|非規則性暫存器集之指令管線化方法|
    US8539462B2|2010-12-21|2013-09-17|National Tsing Hua University|Method for allocating registers for a processor based on cycle information|KR102250089B1|2014-03-11|2021-05-10|삼성전자주식회사|레지스터 포트를 관리하는 방법 및 장치|
    法律状态:
    优先权:
    申请号 | 申请日 | 专利标题
    US13/184,857|US20130024666A1|2011-07-18|2011-07-18|Method of scheduling a plurality of instructions for a processor|
    [返回顶部]